Section: New Results

Characterizing changes in dynamic networks

Very often, dynamic networks are described as time series of graphs. Many works focus on analyzing or capturing into models the properties of the graphs of the series. This approach has a clear limitation : it looses the relationships between the different graphs of the series, which however contain a key information on the dynamics. In order to get more insight in the relationships between the graphs of the series, we analyzed the structure of we call the difference graphs. The difference graph of two consecutive graphs $G_1,G_2$ of the series is the graph whose edge set is the symmetric difference of the edge sets of $G_1$ and $G_2$. In other words, this is exactly the graph of the pairs whose adjacency relationship changed from $G_1$ to $G_2$. We showed that the structure of difference graphs is very particular : their edges are concentrated around a small number of vertices. This shows that the changes between two graphs of the series are not spread everywhere in the network, but are due to changes of the neighborhood of only a small number of nodes of the network. We could show this fact by computing a graph parameter called Minimum Vertex Cover (MVC), which is Np-complete to compute. Using a preprocessing step, we could compute the exact value of this parameter for all difference graphs of real world series. We obtained that the value of the MVC on difference graphs is very small compared to the expected value on a random graph with same density. We also showed that the most commen models of dynamic networks do not capture this property of concentration of edges in the difference graphs of the series. Our result shed light on the way dynamic networks evolve and open the way to significant improvement of existing models.